Theory of Computation
Q42.
Which of the following definitions below generate the same language as L, where L=\{x^ny^n \text{ such that } n\geq 1 \}? I. E \rightarrow xEy\mid xy II. x y \mid (x^+xyy^+) III. x^+y^+Q43.
Consider the languages L1=\{0^{i}1^{j}\;| \; i\neq j\}. L2=\{0^{i}1^{j}\;| \; i=j\}. L3=\{0^{i}1^{j}\;| \; i=2j+1\}. L4=\{0^{i}1^{j}\;| \; i \neq 2j\} Which one of the following statements is true?Q44.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Context-free languages are:Q45.
Context-free languages and regular languages are both closed under the operation (s) of :Q46.
Consider the context-free grammar G below S\rightarrow aSb \;| \;X X\rightarrow aX \;| \;Xb \;|\; a\;|\; b where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S. Which one of the following statements is CORRECT?Q47.
If G is grammar with productions S\rightarrow SaS|aSb|bSa|SS|\epsilon where S is the start variable, then which one of the following is not generated by G?Q48.
Consider the following context-free grammar where the set of terminals is \{a,b,c,d,f\}.\begin{array}{lll} S & \rightarrow & d \: a \: T \mid R \: f \\ T & \rightarrow & a \: S \: \mid \: b \: a \: T \: \mid \epsilon \\ R & \rightarrow & c \: a \: T \: R \: \mid \epsilon \end{array} The following is a partially-filled LL(1) parsing table. Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?Q49.
Consider the following grammar. P\rightarrowxQRS Q\rightarrowyz|zR\rightarroww|\varepsilon S\rightarrowyWhat is FOLLOW (Q) ?Q50.
The language which is generated by the grammar S \rightarrow a S a\mid b S b\mid a\mid b over the alphabet of {a,b} is the set of